package labuladong.leetcode.editor.cn._01linkedlist.ch00;

import labuladong.leetcode.editor.cn._00bean.ListNode;

import static labuladong.leetcode.editor.cn._00utils.LinkedListUtils.print;

public class _160_IntersectionOfTwoLinkedLists {

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) {
     * val = x;
     * next = null;
     * }
     * }
     */
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // p1 指向 A 链表头结点，p2 指向 B 链表头结点
            ListNode p1 = headA, p2 = headB;
            while (p1 != p2) {
                // p1 走一步，如果走到 A 链表末尾，转到 B 链表
                if (p1 == null) p1 = headB;
                else p1 = p1.next;
                // p2 走一步，如果走到 B 链表末尾，转到 A 链表
                if (p2 == null) p2 = headA;
                else p2 = p2.next;
            }
            return p1;
        }

//        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//            int lenA = 0, lenB = 0;
//            // 计算两条链表的长度
//            for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
//                lenA++;
//            }
//            for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
//                lenB++;
//            }
//            // 让 p1 和 p2 到达尾部的距离相同
//            ListNode p1 = headA, p2 = headB;
//            if (lenA > lenB) {
//                for (int i = 0; i < lenA - lenB; i++) {
//                    p1 = p1.next;
//                }
//            } else {
//                for (int i = 0; i < lenB - lenA; i++) {
//                    p2 = p2.next;
//                }
//            }
//            // 看两个指针是否会相同，p1 == p2 时有两种情况：
//            // 1、要么是两条链表不相交，他俩同时走到尾部空指针
//            // 2、要么是两条链表相交，他俩走到两条链表的相交点
//            while (p1 != p2) {
//                p1 = p1.next;
//                p2 = p2.next;
//            }
//            return p1;
//        }

    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new _160_IntersectionOfTwoLinkedLists().new Solution();

        ListNode n5 = new ListNode(5);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(8, n4);
        ListNode n2 = new ListNode(1, n3);
        ListNode n1 = new ListNode(4, n2);

        ListNode n8 = new ListNode(1, n3);
        ListNode n7 = new ListNode(6, n8);
        ListNode n6 = new ListNode(5, n7);

        print(n1);
        print(n6);

        ListNode res = solution.getIntersectionNode(n1, n6);
        System.out.println(res.val);

    }
}
